An arbiter is an interface circuit that controls an electronic communication protocol by assigning priorities to a group of input signals, referred to here as request signals or sometimes just requests, in order to establish a sequence by which the signals are further processed. The priority assignment is typically based on temporal aspects of the request signals, such as the order in which they are asserted at the arbiter's inputs. When the temporal aspects of certain of the request signals are so similar as to exceed the resolution capability of the arbiter, the priority assignment is usually completed by making one or more arbitrary selections and/or following a predetermined coding.
Referring to FIG. 1, it illustrates a conventional four-input asynchronous arbiter such as that described in U.S. Pat. No. 4,835,422. This arbiter is formed with a mutual-exclusion array 10 and a conflict-resolving decoder 12 that together determine which of input request signals R.sub.1 -R.sub.4 (collectively the "R" signals) is to be granted "absolute" priority over all the other R signals for the purposes of further signal processing. The absolute priority determination is based principally on the order in which the R signals are asserted at the arbiter's inputs.
The arbiter in FIG. 1 produces an absolute priority output grant signal G indicative of the absolute priority grant. Absolute priority signal G is a four-bit signal consisting of bits G.sub.1 -G.sub.4 (collectively the "G" bits). Letting i be an integer running from 1 to the number of the last R signal (i.e., 4 here), the value of bit G.sub.i specifically indicates whether request R.sub.i has been granted absolute priority.
ME array 10 contains six substantially identical two-input ME elements 10.sub.1 -10.sub.6 that operate on the R signals to produce six intermediate priority signals I.sub.1 -I.sub.6 (collectively the "I" signals). In particular, each ME element 10.sub.j, where j is an integer running from 1 to the number of the last ME element (i.e., 6 here), receives a different pair of the R signals. Because there are six different pairs of R signals, array 10 thereby covers all the possible pairs of R signals.
Each ME element 10.sub.j operates on its pair of R signals to determine which of the two is to be granted "pairwise" priority over the other when at least one of the two is asserted. ME element 10.sub.j then produces its intermediate priority signal I.sub.j at a value indicative of the pairwise priority determination. Each signal I.sub.j is a two-bit signal consisting of bits I.sub.jA and I.sub.jB. One of bits I.sub.jA and I.sub.jB is used to indicate that one of the pair of R signals to element 10.sub.j has gained pairwise priority between the two signals, while the other of bits I.sub.jA and I.sub.jB serves to indicate that the other R signal has received pairwise priority.
Decoder 12 is formed with suitable logic that decodes the I signals to produce the G bits. In performing the decoding, decoder 12 also resolves priority conflicts that occur when certain of the R signals are asserted so close in time that ME array 10 is unable to supply the I signals at values that uniquely indicate the order in which the R signals were asserted.
For example, consider the pairwise priority determinations involving request signals R.sub.1 -R.sub.3. Assume that they are all asserted and that request R.sub.4 is not asserted. As shown in FIG. 1, ME element 10.sub.1 operates on signal pair R.sub.1 and R.sub.2, ME element 10.sub.2 operates on signal pair R.sub.1 and R.sub.3, and ME element 10.sub.4 operates on signal pair R.sub.2 and R.sub.3. Letting the slash symbol ("/") mean "has beaten" (i.e., "has gained pairwise priority over"), further assume that elements 10.sub.1, 10.sub.4, and 10.sub.2 supply signals I.sub.1, I.sub.4, and I.sub.2 at values respectively indicating that R.sub.1 /R.sub.2, R.sub.2 /R.sub.3, and R.sub.3 /R.sub.1. This constitutes a priority conflict since none of requests R.sub.1 -R.sub.3 is a clear winner over the other two. The logic circuitry in decoder 12 resolves this conflict in a predetermined manner and then supplies grant signal G at an unambiguous value indicating that one of requests R.sub.1 -R.sub.3 is the absolute priority winner.
Note that a "priority" conflict here means a conflict that directly affects the absolute priority determination. Consequently, a priority conflict arises among a specific group of R signals only if those particular signals are true contenders for the absolute priority grant. For instance, in the preceding example, assume that request R.sub.4 is also asserted and that it beats all of requests R.sub.1 -R.sub.3 to get the absolute grant. Even though the I signals still indicate that R.sub.1 /R.sub.2, R.sub.2 /R.sub.3, and R.sub.3 /R.sub.1, there is no priority conflict among requests R.sub.1 -R.sub.3 since none of them can be the absolute priority winner.
The signal path for all priority determinations, regardless of whether priority conflicts need to be resolved or not, goes fully through decode logic 12. The great majority of this logic is utilized solely for handling priority conflicts. However, priority conflicts are normally rare events. For priority determinations that do not require priority-conflict resolution, it is disadvantageous to impose the signal propagation delay through the conflict-resolving logic on the signal propagation delay through the rest of the arbiter.
Even though priority conflicts are relatively rare, a manufacturer or user of an arbiter based on pairwise mutual exclusion would generally like to verify that priority conflicts are resolved according to the format prescribed for the arbiter. The difficulty with doing so is that the requests usually cannot be asserted in such a manner that a given priority conflict is reliably generated. Consequently, a technique for testing the conflict-resolution capability would be quite helpful, especially if the arbiter is designed in a way that significantly avoids having the conflict-resolving propagation delay imposed on the rest of the signal propagation delay for absolute priority determinations not involving conflict resolution.